COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00007 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source
.CB TERM PROJECTS FOR CS206


	The term project is a chance to write a substantial LISP
program and write it up.  A second possibility is to write and prove
correct a LISP program of moderate size.

	It is possible to get a B in the course without a term
project but not an A.  A C project will not help get a B.
The writeup is the primary product that will be graded, so make
it clear what your program does and why.

	Here are some
topics that have been used in the past and may be used again:

.item←0
#. Improving the LCOM4 compiler.  The LCOM4 compiler may be made to
.subitem←0
	&. Compile iterative code when possible.

	&. Compile good arithmetic code.

	&. Compile ⊗label. 

	&. Compile program feature code.

	&. Meet some other deficiency that you notice.

#. Write a compiler that gives very efficient code for arithmetic
expressions.

#. Play a game, e.g. 3-dimensional tic-tac-toe.  If you do
this one, remember to hold individual test runs to a few seconds.
It is very easy to hog the computer by making a tree search one
step deeper.

#. A program to play sequence solitaire.  The game starts with all cards
in the hand, and the object is to get them into the four final piles
with the aid of the four storage piles.  The first final pile wants the
sequence (A 2 3 4 5 6 7 8 9 10 J Q K), the second (2 4 6 8 10 Q A 3 5
7 9 J K), the third (3 6 9 Q 2 5 8 J A 4 7 10 K), and the fourth
(4 8 Q 3 7 J 2 6 10 A 5 9 K).  A move is either playing a card from
the top card from the hand to a storage pile, playing the top card
from the hand to a final pile, or playing the top card on a storage
pile to a final pile.  The top card in the hand may be examined before
deciding what move to make.

#. Make an improved Syntax-directed computation system.

	&. Handle associative and/or commutative expressions.

#. Write and prove correct a 
version of %2samefringe%1 based on
the function %2residue[x,y]%1 that matches the successive atoms of ⊗x and ⊗y
and whose value gives the left-over atoms if there are any:
.skip 1
.begin nofill
.turn off "{"
%2residue[x, y] ← 
	qif x qeq y qthen %1T%2
	qelse qif qat x ∧ qat y qthen %1F%2
	qelse qif qat x qthen {gopher y}[λw.qif x qeq qa w qthen %1R%2 . qd w qelse %1F%2]
	qelse qif qat y qthen {gopher x}[λw.qif y qeq qa w qthen %1L%2 . qd w qelse %1F%2]
	qelse {residue[qa x,qa y]}[λw.
		qif w qeq %1F%2 qthen %1F%2
		qelse residue[qif qa w qeq %1L%2 qthen qd w . qd x qelse qd x,qif qa w qeq %1R%2 qthen qd w . qd y qelse qd y]]%1,
.end


#. Write, define correctness, and prove correct a program for
multiplying permutations.